1. Field of the Invention
This invention relates generally to memory systems for use in data processing equipment and, more particularly, to a memory controller stacking apparatus which accepts and stores commands, instructions, or data generated by a requesting unit until a designated receiving unit is available to receive the information.
2. Prior Art
Modern data processing systems include various subsystems for performing the functions of manipulating, storing and communicating data. Such a system would include, for example, a central processor, a memory, a plurality of input/output (I/O) devices and a control unit. Such data processing systems may differ significantly in configuration; i.e., various functionalities may be located in different subsystems in accordance with particular design criteria. Likewise, the required interface circuitry for communication between the various subsystems may differ both in functionality and operation.
Typically, the central processor manipulates the data in accordance with a series of decodeable instructions called a program. These program instructions are generally retrieved sequentially by the processor and, along with the data which is to be operated upon, are stored in memory devices.
Such memory devices may be of several well known types; however, most commonly used for main memory is a random access device having discrete addressable locations each of which provides storage for a word which may comprise data and/or commands and may contain specific fields useful in a variety of operations. Generally, when the processor is in need of data or instructions, it will generate a memory cycle and provide an address to the memory in order to retrieve the data or word stored in that address.
The series of instructions comprising the program is usually loaded into memory at the beginning of each operation, and occupies a block of memory which normally must not be disturbed or altered until a program has been completed. Data to be operated upon by the processor in accordance with stored instructions is stored in other areas of memory and are retrieved and replaced in accordance with the program instructions.
Communication between the outside world and the data processing system is usually accomplished through the use of a plurality of I/O devices, including such apparatus as magnetic tape handlers, paper tape readers, punch-card readers and remote terminal devices. To control the transfer of information between the I/O devices, an input/output control means is provided which couples the various I/O devices to the processor. The input/output controller coordinates the information flow to and from the various I/O devices and also awards priority when more than one I/O device is attempting to communicate with the rest of the system. Since the I/O devices are usually electromechanical in nature and, as such, are characterized by much lower operating speeds than the remainder of the data processing system, the input/output controller provides buffering to enable the remainder of the processing system to proceed at its normal rate. In many applications, it is advantageous to utilize more than one processor and more than one memory. Likewise, such systems generally require a large number of I/O devices, thus, requiring several input/output controllers.
A memory controller is provided to coordinate communications among the processor, memory devices, and I/O controllers. It receives requests for access to memory as well as specific requests for communications to other subsystems. The memory controller coordinates the execution of operations and transfers of information and may also provide a means for assigning priority when requests for access to memory are generated by more than one subsystem.
A typical data processing system may contain a single memory controller; however, multicomputer configurations may utilize several memory controllers.
In those environments wherein more than one memory controller is employed, each of the memory controllers is independent from each other and they function simultaneously thus providing parallelism in accessing of the memory system. Each memory controller will temporarily store requests from the processors and input/output controllers and generally service these subsystems in accordance with a priority scheme. Data transfers between the various communicating devices and the memory controller are word oriented, e.g., 40 bits. Typical data processing systems employing memory controllers are shown and described in U.S. Pat. No. 3,413,613, entitled "Reconfigurable Data Processing System".
The instructions and/or commands and/or data which are forwarded to the memory controller are accepted and temporarily stored in a stack comprised of a plurality of registers until the appropriate destination units are available to process the information. Once stacked, the instructions or commands are generally forwarded to the destination units on a First In/First Out basis. A write counter determines which register in the stack receives the incoming information and a read counter selects the register whose contents are to be passed on to its destination unit next. The presence of a command in the stack is usually detected by comparing the contents of the write counter to the contents of the read counter. If they are unequal, this indicates that the stack contains information to be passed on. The write counter is advanced when a request is received by the memory controller, and the read counter is advanced when the information is passed from the stack to the destination unit. If the destination unit corresponding to the next command to be read out of the stack is busy, other commands which occupy a lower position in the stack cannot be forwarded even if their particular destination units are free. Thus, one busy destination unit can effectively block commands destined for free units. This is clearly inefficient and accounts for undue delays in a technology where speed may be of utmost importance.
Further, since the stack has a finite depth (or number of levels), the danger exists that the write counter will exhaust all available locations in the stack and will wrap around upon itself thus writing new information into a stack location before the contents of that location have been forwarded to its destination unit. If this overflow occurs, the contents of the register or registers in question is lost resulting in a system error. Using the above described approach, it is difficult to determine when the stack becomes full with information that has not been forwarded to the respective destination units. Further, since this arrangement operates sequentially, it is difficult to determine how busy the stack actually is, i.e., an indication of throughput.